﻿/*
 * link_last_next.hpp
 *
 *  Created on: 2020年2月25日
 *      Author: Dylan.Gao
 */

#ifndef _DM_LINK_LAST_NEXT_HPP_
#define _DM_LINK_LAST_NEXT_HPP_

#include <dm/link_base.hpp>
#include <dm/sparce_color.hpp>

namespace dm{

/**
 * 双向链表
 */
template<typename T>
class TCLinkLastNext:public TCLinkBase<T>{
public:
	typedef TCLinkLastNext<T> list_t;
	TCLinkLastNext( T v,list_t* last=NULL,list_t* next=NULL ):TCLinkBase<T>(v),m_last(last),m_next(next){
	}

	/**
	 * 析构整个链表
	 */
	virtual ~TCLinkLastNext(){
		// 先解开链
		if( m_last )
			m_last->m_next = NULL;
		if( m_next )
			m_next->m_last = NULL;

		if( m_last )
			delete m_last;
		if( m_next )
			delete m_next;
	}

	inline const list_t* last()const{
		return m_last;
	}

	inline list_t* last(){
		return m_last;
	}

	inline const list_t* next()const{
		return m_next;
	}

	inline list_t* next(){
		return m_next;
	}

	void insertLast( T v ){
		list_t* l = new list_t(v);
		l->m_next = this;
		l->m_last = m_last;

		m_last = l;
		if( l->m_last )
			l->m_last->m_next = l;
	}

	/**
	 * 插入链表
	 * @param l 不可以环
	 * @return
	 */
	bool insertLast( list_t* l ){
		if( l==NULL )
			return false;

		list_t* ll = l->lastEnd();
		if( ll==NULL )	// 有环
			return false;

		list_t* ln = l->nextEnd();
		if( ln==NULL )	// 有环
			return false;

		ll->m_last = m_last;
		ln->m_next = this;

		if( m_last )
			m_last->m_next = ll;

		m_last = ln;

		return true;
	}

	void insertNext( T v ){
		list_t* l = new list_t(v);
		l->m_last = this;
		l->m_next = m_next;

		if( m_next )
			m_next->m_last = l;
		m_next = l;
	}

	bool insertNext( list_t* l ){
		if( l==NULL )
			return false;

		list_t* ll = l->lastEnd();
		if( ll==NULL )	// 环
			return false;

		list_t* ln = l->nextEnd();
		if( ln==NULL )	// 环
			return false;

		ll->m_last = this;
		ln->m_next = m_next;

		if( m_next )
			m_next->m_last = ln;
		m_next = ll;
		return true;
	}

	/**
	 * 追加到末尾
	 * 并返回当前指针
	 * @param v
	 * @return
	 */
	list_t* pushBack( T v ){
		list_t* l = nextEnd();
		if( l ){
			l->insertNext(v);
			return this;
		}

		return NULL;
	}

	/**
	 * 追加到末尾
	 * 并返回当前指针
	 * @param l
	 * @return
	 */
	list_t* pushBack( list_t* l ){
		list_t* e = nextEnd();
		if( e ){
			if( e->insertNext(l) )
				return this;
		}

		return NULL;
	}

	list_t* pushHead( T v ){
		list_t* l = lastEnd();
		if( l ){
			l->insertLast(v);
			return l->last();
		}

		return NULL;
	}

	inline list_t* pushHead( list_t* l ){
		return l->pushBack(this);
	}

	bool removeLast(){
		list_t* l = m_last;
		if( l ){
			m_last = l->m_last;
			if( m_last )
				m_last->m_next = this;

			l->m_next = NULL;
			l->m_last = NULL;
			delete l;
			return true;
		}
		return false;
	}

	bool removeNext(){
		list_t* l = m_next;
		if( l ){
			m_next = l->m_next;
			if( m_next )
				m_next->m_last = this;

			l->m_next = NULL;
			l->m_last = NULL;
			delete l;
			return true;
		}
		return false;
	}

	bool removeLasts(){
		if( m_last==NULL )
			return false;	// 不存在

		list_t* l = lastEnd();
		if( l==NULL )	// 环
			return false;

		m_last->m_next = NULL;
		m_last = NULL;
		delete l;

		return true;
	}

	bool removeNexts(){
		if( m_next==NULL )
			return false;

		list_t* l = nextEnd();
		if( l==NULL )	// 环
			return false;

		m_next->m_last = NULL;
		m_next = NULL;
		delete l;

		return true;
	}

	list_t* popNext(){
		list_t* l = m_next;
		if( l ){
			m_next = l->m_next;
			if( m_next )
				m_next->m_last = this;
			l->m_next = NULL;
			l->m_last = NULL;
		}

		return l;
	}

	list_t* popLast(){
		list_t* l = m_last;
		if( l ){
			m_last = l->m_last;
			if( m_last )
				m_last->m_next = this;
			l->m_next = NULL;
			l->m_last = NULL;
		}

		return l;
	}

	list_t* popLasts(){
		list_t* l = m_last;
		if( l ){
			l->m_next = NULL;
			m_last = NULL;
		}

		return l;
	}

	list_t* popNexts(){
		list_t* l = m_next;
		if( l ){
			l->m_last = NULL;
			m_next = NULL;
		}

		return l;
	}

	list_t* reverse(){
		TCSparceColor<dm::ptr_t> m;

		list_t* l = m_last;
		list_t* n = m_next;
		list_t* p = this;

		list_t* t;
		t = p->m_last;
		p->m_last = p->m_next;
		p->m_next = t;
		m.add(dm::ptr_t(p));

		while( l ){
			p = l;
			if( false==m.add(dm::ptr_t(p)) )	// 环
				return this;

			l = p->m_last;

			t = p->m_last;
			p->m_last = p->m_next;
			p->m_next = t;
		}

		while( n ){
			p = n;
			if( false==m.add(dm::ptr_t(p)) )	// 环
				return this;

			n = p->m_next;

			t = p->m_last;
			p->m_last = p->m_next;
			p->m_next = t;
		}

		return this;
	}

	/**
	 * 是否为环
	 * @return
	 */
	bool isRing()const{
		TCSparceColor<dm::ptr_t> m;

		m.add(dm::ptr_t(this));

		list_t* l = m_last;
		while( l ){
			if( m.add(dm::ptr_t(l))==false )
				return true;
			l = l->m_last;
		}

		return false;
	}

	inline list_t* lastEnd(){
		return lastEnd(this);
	}

	inline const list_t* lastEnd()const{
		return lastEnd(this);
	}

	inline list_t* nextEnd(){
		return nextEnd(this);
	}

	inline const list_t* nextEnd()const{
		return nextEnd(this);
	}

	/**
	 * 节点数
	 * @return
	 */
	unsigned int size()const{
		TCSparceColor<dm::ptr_t> m;
		m.add(dm::ptr_t(this));
		unsigned int rt = 1;

		const list_t* l = m_last;
		while( l ){
			if( false==m.add(dm::ptr_t(l)) )
				return rt;
			++rt;
			l = l->m_last;
		}

		l = m_next;
		while( l ){
			if( false==m.add(dm::ptr_t(l)) )
				return rt;
			++rt;
			l = l->m_next;
		}

		return rt;
	}

	/**
	 * last侧节点数，不含本节点
	 * @return
	 */
	unsigned int lastSize()const{
		TCSparceColor<dm::ptr_t> m;
		m.add(dm::ptr_t(this));
		unsigned int rt = 0;
		const list_t* l = m_last;
		while( l ){
			if( false==m.add(dm::ptr_t(l)) )
				return rt;
			++rt;
			l = l->m_last;
		}

		return rt;
	}

	/**
	 * next侧节点数，不含本节点
	 * @return
	 */
	unsigned int nextSize()const{
		TCSparceColor<dm::ptr_t> m;
		m.add(dm::ptr_t(this));
		unsigned int rt = 0;
		const list_t* l = m_next;
		while( l ){
			if( false==m.add(dm::ptr_t(l)) )
				return rt;
			++rt;
			l = l->m_next;
		}

		return rt;
	}

	/**
	 * 根据索引号获取节点
	 * @param idx
	 * @return
	 */
	list_t* getLastByIndex( const unsigned int& idx ){
		return getLastByIndex(this,idx);
	}

	/**
	 * 根据索引号获取节点
	 * @param idx
	 * @return
	 */
	const list_t* getLastByIndex( const unsigned int& idx )const{
		return getLastByIndex(this,idx);
	}

	/**
	 * 根据索引号获取节点
	 * @param idx
	 * @return
	 */
	list_t* getNextByIndex( const unsigned int& idx ){
		return getNextByIndex(this,idx);
	}

	/**
	 * 根据索引号获取节点
	 * @param idx
	 * @return
	 */
	const list_t* getNextByIndex( const unsigned int& idx )const{
		return getNextByIndex(this,idx);
	}
protected:
	template<typename TList>
	TList lastEnd( TList l )const{
		if( l==NULL )
			return NULL;

		dm::TCSparceColor<dm::ptr_t> m;
		m.add(dm::ptr_t(l));
		while( l->m_last ){
			l = m_last;
			if( false==m.add(dm::ptr_t(l)) )
				return NULL;	// 环
		}

		return l;
	}

	template<typename TList>
	TList nextEnd( TList l )const{
		if( l==NULL )
			return NULL;

		dm::TCSparceColor<dm::ptr_t> m;
		m.add(dm::ptr_t(l));
		while( l->m_next ){
			l = m_next;
			if( false==m.add(dm::ptr_t(l)) )
				return NULL;	// 环
		}

		return l;
	}

	template<typename TList>
	TList getLastByIndex( TList l,const unsigned int& idx )const{
		for( unsigned int i=0;i<idx;++i ){
			if( l==NULL )
				return NULL;
			l = l->m_last;
		}

		return l;
	}

	template<typename TList>
	TList getNextByIndex( TList l,const unsigned int& idx )const{
		for( unsigned int i=0;i<idx;++i ){
			if( l==NULL )
				return NULL;
			l = l->m_next;
		}

		return l;
	}

protected:
	list_t* m_last;
	list_t* m_next;
};

}

#endif /* INCLUDE_DM_LINK_LAST_NEXT_HPP_ */
